#include "string_array.h"
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

myStr::myStr(const char* str){
    length = strlen(str);
    // 分配足够的空间并存储长度信息
    data = new char[length + 2];
    data[0] = length; // 第一个位置存储字符串长度
    // 复制字符串内容到 data
    for (int i = 0; i < length; ++i) {
        data[i + 1] = str[i];
    }
    data[length + 1] = '\0'; // 添加终止字符 '\0'
    next = new int[length +1];
    nextVal = new int[length +1];
}

myStr::myStr() : data(nullptr), length(0), next(nullptr), nextVal(nullptr) {}

myStr::~myStr() {
    delete[] data;
    delete[] next;
    delete[] nextVal;
}

void myStr::print(){
    for(int i = 1; i <= data[0]; i++)
        cout << data[i];
    cout << endl;
}

// 生成KMP的next数组
void myStr::kmp_next() {
    if (next != nullptr) delete[] next;  // 避免重复分配
    next = new int[length + 1];              // 分配空间
    next[0] = 0,next[1] = 0;                         // 初始化第一个元素
    int i = 1,j = 0;
    while(i < length){
        if(j == 0 || data[i] == data[j]){++i,++j;next[i] = j;}
        else j = next[j];
    }
}

// 生成KMP nextVal数组
void myStr::kmp_nextVal() {
    if (nextVal != nullptr) delete[] nextVal;  // 避免重复分配
    nextVal = new int[length + 1];                 // 分配空间
    nextVal[0] = 0,nextVal[1] = 0;
    int i = 1,j = 0;
    while(i < length){
        if(j == 0 ||data[i] == data[j]){
            ++i,++j;
            if(data[i] != data[j]) nextVal[i] = j;
            else nextVal[i] = nextVal[j];
        }
        else j = nextVal[j];
    }
}

void myStr::printNext(){
    for(int i = 1; i <= length; i++)
        cout << next[i];
    cout << endl;
}

void myStr::printNextVal(){
    for(int i = 1; i <= length; i++)
        cout << nextVal[i];
    cout << endl;
}

bool replaceStr(myStr& S, const int& start, const myStr& T, const myStr& V) {
    for (int i = start; i <= S.length - T.length + 1; i++){
        int j = 0,a = 0;
        for (j = 1, a = i; j <= T.length; j++, a++){
            if (S.data[a] != T.data[j])
            break;
        }
        if (j > T.length){
            int pos = i;
            int newlength = S.length + V.length - T.length;
            char* newdata = new char[newlength + 2];//建立一个新串，暂存数据
            newdata[0] = newlength;
            for (int a = 1; a < pos; a++){
                newdata[a] = S.data[a];//复制匹配位置之前的主串
            }
            for (int a = pos, b = 1; b <= V.length; a++, b++){
                newdata[a] = V.data[b];//复制替换串
            }
            for (int a = pos + V.length, b = pos + T.length; a <= newlength; a++, b++){
                newdata[a] = S.data[b];//复制匹配模式串后的主串
            }
            delete[] S.data;
            S.data = newdata;
            S.length = newlength;
            return 1;
        }
    }
    return 0;
}

void myMatrix::printMatrix(){
    sort(nodeList, nodeList + nodeNum, compareNodes);
    cout << rowNum << "," << colNum << "," << nodeNum << endl;
    for(int i = 0; i < nodeNum; i++)
        cout << nodeList[i].row << "," << nodeList[i].col << "," << nodeList[i].value << endl;
}

int kmpMatch(const myStr& S, const myStr& T) {
    if (T.length == 0 || S.length < T.length) return -1;
    int i = 1,j = 1;
    while (i <= S.length && j <= T.length){
        if (j == 0 || S.data[i] == T.data[j])
        i++,j++;//字符相等，下移一位
        else
        j = T.nextVal[j];//不匹配，跳到nextval数组位置
    }
    if (j > T.length)
    return i - T.length;
    else
    return -1;
}

int simpleMatch(const myStr& S, const myStr& T) {
    // 若 T 的长度大于 S 的长度，不可能有匹配。
    if (T.length == 0 || S.length < T.length) return -1;
    for (int i = 1; i <= S.length - T.length + 1; i++){
        int j = 0,a = 0;
        for (j = 1,a = i; j <= T.length; j++,a++){
            if (S.data[a] != T.data[j])
            break;//如果不匹配，跳出循环
        }
        if (j > T.length)
        return i;//匹配时，返回位置
    }
    return -1;
}

// 默认构造函数，实现空矩阵初始化
myMatrix::myMatrix() {
    rowNum = 0;
    colNum = 0;
    nodeNum = 0;
    nodeList = nullptr;  // 没有元素时指针设为 nullptr
}

// 带参数的构造函数：根据给定的行数、列数、非零元素个数及三元组数据初始化矩阵
myMatrix::myMatrix(const int& rNum, const int& cNum, const int& nNum, const int* data) {
    rowNum = rNum;
    colNum = cNum;
    nodeNum = nNum;
    nodeList = new matrixNode[nodeNum];
    for (int i = 0; i < nodeNum; ++i) {
        nodeList[i].row = data[i * 3];
        nodeList[i].col = data[i * 3 + 1];
        nodeList[i].value = data[i * 3 + 2];
    }
}

// 析构函数：释放动态分配的内存
myMatrix::~myMatrix() {
    delete[] nodeList;
}

// 快速转置算法：将当前矩阵的转置结果存储在矩阵T中
void myMatrix::FastTransposeSMatrix(myMatrix& T) {
    T.rowNum = colNum;
    T.colNum = rowNum;
    T.nodeNum = nodeNum;
    T.nodeList = new matrixNode[nodeNum];

    // 统计每一列中的非零元素数量
    int* colCounts = new int[colNum]();
    for (int i = 0; i < nodeNum; ++i) {
        ++colCounts[nodeList[i].col];
    }

    // 计算每列的起始位置
    int* colStart = new int[colNum]();
    for (int i = 1; i < colNum; ++i) {
        colStart[i] = colStart[i - 1] + colCounts[i - 1];
    }

    // 将节点放置到转置矩阵的相应位置
    for (int i = 0; i < nodeNum; ++i) {
        int col = nodeList[i].col;
        int pos = colStart[col];

        T.nodeList[pos].row = nodeList[i].col;
        T.nodeList[pos].col = nodeList[i].row;
        T.nodeList[pos].value = nodeList[i].value;
        
        ++colStart[col];
    }

    delete[] colCounts;
    delete[] colStart;
} 